

def edit_distance(fromWord, toWord):
    d = {}
    lenstr1 = len(fromWord)
    lenstr2 = len(toWord)
    for i in xrange(-1, lenstr1 + 1):
        d[(i, -1)] = i + 1
    for j in xrange(-1, lenstr2 + 1):
        d[(-1, j)] = j + 1
    for i in xrange(lenstr1):
        for j in xrange(lenstr2):
            if fromWord[i] == toWord[j]:
                cost = 0
            else:
                cost = 1
            d[(i, j)] = min(
                           d[(i - 1, j)] + 1,  # deletion
                           d[(i, j - 1)] + 1,  # insertion
                           d[(i - 1, j - 1)] + cost,  # substitution
                          )
            if i and j and fromWord[i] == toWord[j - 1]:
                if fromWord[i - 1] == toWord[j]:
                    d[(i, j)] = min(d[(i, j)], d[i - 2, j - 2] + cost)
    return d[lenstr1 - 1, lenstr2 - 1]


def findBestCandidates(fromWord, wordList):
    from operator import itemgetter
    minEditDistance = 10
    result = []
    for toWord in wordList:
        distance = edit_distance(fromWord, toWord)
        if distance == minEditDistance:
            result.append((toWord, wordList[toWord]))
        elif distance < minEditDistance:
            minEditDistance = distance
            result = []
            result.append((toWord, wordList[toWord]))
    result = sorted(result, key=itemgetter(1), reverse=True)
    return result


def main():
    import argparse
    import sys
    import time
    parser = argparse.ArgumentParser(description='recieve word, threshold'
                                     ' and lookup the db andcalculate the'
                                     ' best correct words and prints it'
                                     ' with it\'s freq')
    parser.add_argument('--db_file',
                        dest='db_file',
                        action='store',
                        nargs='?',
                        type=argparse.FileType('r'),
                        default=sys.stdin)
    parser.add_argument('words',
                        action='store',
                        nargs='+',
                        default=[],
                        help='words for spell check')
    args = parser.parse_args()
    print args.words
    import notspeller_db
    db = notspeller_db.Database(args.db_file)

#     db.print_all()
    for word in args.words:
        t0 = time.clock()
        result = findBestCandidates(word, db.lookup(word))
        t1 = time.clock()
        print word, " - ", result
        print 'Time: ' + str(t1 - t0) + ' seconds'

if __name__ == "__main__":
    main()
